Secure multiparty computation (SMC) is an area of cryptography concerned with providing multiple parties with the protocols for jointly computing a function over their inputs, while keeping the inputs private. Each party is presumed to possess private data that the party does not want to reveal to anyone else. One type of SMC protocol allows the parties to compute a combined or aggregate value using a public data sharing function for jointly sharing their respective private data while ensuring that their individual privacy is preserved.
Secret sharing is one form of SMC protocol. Secret sharing can be used, for example, for secure data storage or computing an aggregate value. Consider secure data storage. Here, a secret is split or shared across the computers of multiple users and each secret share is used in the public data sharing function. All, or a subset, of the secret shares are required to reconstruct the secret. Secret sharing is considered to be more secure than other forms of data security that rely on the storage of a secret on a single computer, as a compromise of any one computer will only leak a part of the secret.
Secret sharing has also been used in the context of online private data sharing. Here, a public function is considered secure if no party can learn any more from the description of the public function and the resultant aggregate value than what could be learned from knowledge of their own data. Parties may desire to permit the revelation of their personal information only under a veil of privacy that disassociates the private data from the contributing party. For instance, many online service providers harvest personal indicia, such as mobility, application usage patterns, browsing history, and social interactions, to build detailed user profiles that can be of potential value to advertisers and businesses. Despite being tracked and profiled, users invariably are not compensated for their private data contributions and online service providers often justify data harvesting as falling under their terms of service.
Until recently, by lacking an active role in the process, users have had little choice but to trust their service providers with their personal data, despite the risk to and loss of their privacy. However, secret sharing has provided one way for users to tolerate the seemingly-inevitable harvesting of their personal data by allowing users to instead offer a model or “gist” of their personal data in a privacy-preserving way. With secret sharing, each user encrypts his private data using a share of a secret. A central data aggregator combines the users' individually encrypted private data into an aggregate value that, upon being decrypted, provides a value representative of the private data without revealing either each user's identity or the actual value of their data contribution. For instance, some secret sharing schemes allow the central aggregator to obtain the sum of all private data contributions without knowledge of each specific input.
Conventionally, secret sharing assumes either trust or participant collaboration for secret establishment. For instance, U.S. Patent App. Pub. No. 2010/0054480, published Mar. 4, 2010, to Schneider, describes sharing a secret using polynomials over polynomials. In one embodiment, N shares of a secret are distributed by a distributor among cooperating entities by representing the secret as a secret polynomial over GF(q), where q is a prime number or power of a prime number. A splitting polynomial of degree (K−1) over GF(qm) is then constructed, where K is the number of shares necessary to reconstruct the secret and m is a positive integer. To reconstruct the secret, a reconstructor collects secret shares to form interpolating polynomials, and linearly combines the interpolating polynomials to recover the splitting polynomial. The original secret can then be extracted from the splitting polynomial. However, Schneider assumes the existence of a trusted entity willing to generate a splitting polynomial and that users are willing to cooperate with each other, which may be an unrealistic adversarial model.
U.S. Pat. No. 7,167,565, issued Jan. 23, 2007, to Rajasekaran, describes efficient techniques for sharing a secret. In one embodiment, a custodian computes n unique keys to be distributed to users and an exponentiated version of the secret. After key generation, the custodian deletes the secret itself and, following key distribution, also deletes its copies of the n unique keys. To reconstruct the secret, k of the n users must transmit their keys back to custodian. However, the custodian has no ability to reconstruct the secret without the collaboration and cooperation of at least k of the users and, as with Schneider, assuming such user cooperation may be an unrealistic adversarial model.
E. Shi et al., “Privacy-Preserving Aggregation of Time-Series Data,” Net. and Distrib. Sys. Sec. Symp. (February 2011), describes a privacy mechanism, such that, for every time period, a data aggregator is able to learn some aggregate statistic, but not each participant's value, even when the aggregator has arbitrary auxiliary information. A group of participants periodically uploads encrypted values to the data aggregator, who is able to compute the sum of all participants' values in each time period, but is unable to learn anything else. However, Shi assumes a trusted data aggregator able to generate secret keys for each participant and itself and, after distributing a key to each user, the same data aggregator would destroy all participants' keys and retain only one extra key for itself.
Other secret sharing schemes, such as described in T. Jung et al., “Data Aggregation Without Secure Channel: How to Evaluate a Multivariate Polynomial Securely,” arXiv:1206:2660 (June 2012), and K. Xing et al., “Mutual Privacy Preserving Regression Modeling in Participatory Sensing,” IEEE INFOCOM (April 2013) require participants to interact in a pairwise fashion to agree on secret shares, but such schemes scale quadratically with the number of participants and are impracticable in all but the smallest of populations.
Therefore, a need remains for an approach to forming secret shares that is both scalable and does not rely on blindly trusting a central data aggregator.